//
// Created by Tan Ke on 2024/2/17.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int robHelper(int* nums, int* record, int numsSize, int currentIndex)
{
    if (currentIndex == 0) {
        record[0] = nums[0];
        return nums[0];
    }

    if (currentIndex == 1) {
        if (nums[1] > nums[0]) {
            record[1] = nums[1];
            return nums[1];
        } else {
            record[1] = nums[0];
            return nums[0];
        }
    }

    if (record[currentIndex] != -1) {
        return record[currentIndex];
    } else {
        int preVal_1 = robHelper(nums, record, numsSize, currentIndex - 1);
        int preVal_2 = robHelper(nums, record, numsSize, currentIndex - 2) + nums[currentIndex];
        if (preVal_1 > preVal_2) {
            record[currentIndex] = preVal_1;
            return preVal_1;
        } else {
            record[currentIndex] = preVal_2;
            return preVal_2;
        }
    }
}

int rob(int* nums, int numsSize)
{
    int* record = (int*)malloc(sizeof(int) * numsSize);
    memset(record, -1, sizeof(int) * numsSize);

    int result = robHelper(nums, record, numsSize, numsSize - 1);
    return result;
}

int main(void)
{
    int nums1[4] = {1, 2, 3, 1};
    printf("%d\n", rob(nums1, 4));

    int nums2[5] = {2, 7, 9, 3, 1};
    printf("%d\n", rob(nums2, 5));

    return 0;
}